

<!DOCTYPE html>
<!--[if IE 8]><html class="no-js lt-ie9" lang="en" > <![endif]-->
<!--[if gt IE 8]><!--> <html class="no-js" lang="en" > <!--<![endif]-->
<head>
  <meta charset="utf-8">
  
  <meta name="viewport" content="width=device-width, initial-scale=1.0">
  
  <title>toydata.LinkedLists &mdash; ToyData 1.0 documentation</title>
  

  
  
  
  

  
  <script type="text/javascript" src="../../_static/js/modernizr.min.js"></script>
  
    
      <script type="text/javascript" id="documentation_options" data-url_root="../../" src="../../_static/documentation_options.js"></script>
        <script type="text/javascript" src="../../_static/jquery.js"></script>
        <script type="text/javascript" src="../../_static/underscore.js"></script>
        <script type="text/javascript" src="../../_static/doctools.js"></script>
        <script type="text/javascript" src="../../_static/language_data.js"></script>
    
    <script type="text/javascript" src="../../_static/js/theme.js"></script>

    

  
  <link rel="stylesheet" href="../../_static/css/theme.css" type="text/css" />
  <link rel="stylesheet" href="../../_static/pygments.css" type="text/css" />
    <link rel="index" title="Index" href="../../genindex.html" />
    <link rel="search" title="Search" href="../../search.html" /> 
</head>

<body class="wy-body-for-nav">

   
  <div class="wy-grid-for-nav">
    
    <nav data-toggle="wy-nav-shift" class="wy-nav-side">
      <div class="wy-side-scroll">
        <div class="wy-side-nav-search" >
          

          
            <a href="../../index.html" class="icon icon-home"> ToyData
          

          
          </a>

          
            
            
              <div class="version">
                1.0
              </div>
            
          

          
<div role="search">
  <form id="rtd-search-form" class="wy-form" action="../../search.html" method="get">
    <input type="text" name="q" placeholder="Search docs" />
    <input type="hidden" name="check_keywords" value="yes" />
    <input type="hidden" name="area" value="default" />
  </form>
</div>

          
        </div>

        <div class="wy-menu wy-menu-vertical" data-spy="affix" role="navigation" aria-label="main navigation">
          
            
            
              
            
            
              <p class="caption"><span class="caption-text">Contents:</span></p>
<ul>
<li class="toctree-l1"><a class="reference internal" href="../../Intro.html">Introductions</a></li>
<li class="toctree-l1"><a class="reference internal" href="../../Overview.html">Overview</a></li>
<li class="toctree-l1"><a class="reference internal" href="../../modules.html">toydata</a></li>
</ul>

            
          
        </div>
      </div>
    </nav>

    <section data-toggle="wy-nav-shift" class="wy-nav-content-wrap">

      
      <nav class="wy-nav-top" aria-label="top navigation">
        
          <i data-toggle="wy-nav-top" class="fa fa-bars"></i>
          <a href="../../index.html">ToyData</a>
        
      </nav>


      <div class="wy-nav-content">
        
        <div class="rst-content">
        
          















<div role="navigation" aria-label="breadcrumbs navigation">

  <ul class="wy-breadcrumbs">
    
      <li><a href="../../index.html">Docs</a> &raquo;</li>
        
          <li><a href="../index.html">Module code</a> &raquo;</li>
        
      <li>toydata.LinkedLists</li>
    
    
      <li class="wy-breadcrumbs-aside">
        
      </li>
    
  </ul>

  
  <hr/>
</div>
          <div role="main" class="document" itemscope="itemscope" itemtype="http://schema.org/Article">
           <div itemprop="articleBody">
            
  <h1>Source code for toydata.LinkedLists</h1><div class="highlight"><pre>
<span></span><span class="kn">from</span> <span class="nn">toydata.utils</span> <span class="kn">import</span> <span class="n">Empty</span>
<span class="kn">from</span> <span class="nn">typing</span> <span class="kn">import</span> <span class="n">Optional</span>


<div class="viewcode-block" id="Node"><a class="viewcode-back" href="../../toydata.html#toydata.LinkedLists.Node">[docs]</a><span class="k">class</span> <span class="nc">Node</span><span class="p">:</span>
    <span class="sd">&quot;&quot;&quot;</span>
<span class="sd">    Node in Single linked list.</span>
<span class="sd">    &quot;&quot;&quot;</span>
    <span class="k">def</span> <span class="fm">__init__</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">value</span><span class="p">):</span>
        <span class="bp">self</span><span class="o">.</span><span class="n">value</span> <span class="o">=</span> <span class="n">value</span>
        <span class="bp">self</span><span class="o">.</span><span class="n">next</span><span class="p">:</span> <span class="n">Optional</span><span class="p">[</span><span class="s1">&#39;Node&#39;</span><span class="p">]</span> <span class="o">=</span> <span class="kc">None</span>

    <span class="k">def</span> <span class="fm">__str__</span><span class="p">(</span><span class="bp">self</span><span class="p">):</span>
        <span class="sd">&quot;&quot;&quot;Show the node in single linked list properly&quot;&quot;&quot;</span>
        <span class="k">return</span> <span class="sa">f</span><span class="s2">&quot;Node(</span><span class="si">{self.value}</span><span class="s2">)&quot;</span></div>


<div class="viewcode-block" id="Singlellist"><a class="viewcode-back" href="../../toydata.html#toydata.LinkedLists.Singlellist">[docs]</a><span class="k">class</span> <span class="nc">Singlellist</span><span class="p">:</span>
    <span class="sd">&quot;&quot;&quot;</span>
<span class="sd">    The implementation of single linked list.</span>
<span class="sd">    &quot;&quot;&quot;</span>

    <span class="k">def</span> <span class="fm">__init__</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">items</span><span class="o">=</span><span class="kc">None</span><span class="p">):</span>
        <span class="bp">self</span><span class="o">.</span><span class="n">head</span> <span class="o">=</span> <span class="kc">None</span>
        <span class="bp">self</span><span class="o">.</span><span class="n">tail</span> <span class="o">=</span> <span class="kc">None</span>
        <span class="bp">self</span><span class="o">.</span><span class="n">size</span> <span class="o">=</span> <span class="mi">0</span>
        <span class="k">if</span> <span class="n">items</span><span class="p">:</span>
            <span class="k">for</span> <span class="n">item</span> <span class="ow">in</span> <span class="n">items</span><span class="p">:</span>
                <span class="bp">self</span><span class="o">.</span><span class="n">add_last</span><span class="p">(</span><span class="n">item</span><span class="p">)</span>

    <span class="k">def</span> <span class="fm">__len__</span><span class="p">(</span><span class="bp">self</span><span class="p">):</span>
        <span class="sd">&quot;&quot;&quot;The length of the list.</span>

<span class="sd">        Time complexity: O(1)</span>
<span class="sd">        &quot;&quot;&quot;</span>
        <span class="k">return</span> <span class="bp">self</span><span class="o">.</span><span class="n">size</span>

    <span class="k">def</span> <span class="fm">__str__</span><span class="p">(</span><span class="bp">self</span><span class="p">):</span>
        <span class="sd">&quot;&quot;&quot;Show the list properly.</span>

<span class="sd">        Time complexity: O(n)</span>
<span class="sd">        &quot;&quot;&quot;</span>
        <span class="n">items</span> <span class="o">=</span> <span class="p">[]</span>
        <span class="n">pointer</span> <span class="o">=</span> <span class="bp">self</span><span class="o">.</span><span class="n">head</span>
        <span class="k">while</span> <span class="n">pointer</span> <span class="ow">is</span> <span class="ow">not</span> <span class="kc">None</span><span class="p">:</span>
            <span class="n">items</span><span class="o">.</span><span class="n">append</span><span class="p">(</span><span class="n">pointer</span><span class="o">.</span><span class="n">value</span><span class="p">)</span>
            <span class="n">pointer</span> <span class="o">=</span> <span class="n">pointer</span><span class="o">.</span><span class="n">next</span>
        <span class="k">return</span> <span class="sa">f</span><span class="s2">&quot;SLL</span><span class="si">{items}</span><span class="s2">&quot;</span>

    <span class="k">def</span> <span class="fm">__contains__</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">value</span><span class="p">):</span>
        <span class="sd">&quot;&quot;&quot;</span>
<span class="sd">        Check if there is a value in the list, support for `in`</span>

<span class="sd">        Time complexity: O(n)</span>
<span class="sd">        &quot;&quot;&quot;</span>
        <span class="n">points</span> <span class="o">=</span> <span class="bp">self</span><span class="o">.</span><span class="n">head</span>
        <span class="k">while</span> <span class="n">points</span> <span class="ow">is</span> <span class="ow">not</span> <span class="kc">None</span><span class="p">:</span>
            <span class="k">if</span> <span class="n">points</span><span class="o">.</span><span class="n">value</span> <span class="o">==</span> <span class="n">value</span><span class="p">:</span>
                <span class="k">return</span> <span class="kc">True</span>
            <span class="n">points</span> <span class="o">=</span> <span class="n">points</span><span class="o">.</span><span class="n">next</span>
        <span class="k">return</span> <span class="kc">False</span>

    <span class="k">def</span> <span class="fm">__getitem__</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">index</span><span class="p">):</span>
        <span class="sd">&quot;&quot;&quot;Get the element by index, sll[index]</span>

<span class="sd">        Time complexity: O(n)</span>
<span class="sd">        &quot;&quot;&quot;</span>
        <span class="k">assert</span> <span class="mi">0</span> <span class="o">&lt;=</span> <span class="n">index</span> <span class="o">&lt;=</span> <span class="p">(</span><span class="nb">len</span><span class="p">(</span><span class="bp">self</span><span class="p">)</span> <span class="o">-</span> <span class="mi">1</span><span class="p">),</span> <span class="s2">&quot;Index out of range&quot;</span>
        <span class="n">p</span> <span class="o">=</span> <span class="bp">self</span><span class="o">.</span><span class="n">head</span>
        <span class="k">while</span> <span class="n">index</span> <span class="o">&gt;</span> <span class="mi">0</span><span class="p">:</span>
            <span class="n">p</span> <span class="o">=</span> <span class="n">p</span><span class="o">.</span><span class="n">next</span>
            <span class="n">index</span> <span class="o">-=</span> <span class="mi">1</span>
        <span class="k">return</span> <span class="n">p</span><span class="o">.</span><span class="n">value</span>

    <span class="k">def</span> <span class="fm">__setitem__</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">index</span><span class="p">,</span> <span class="n">val</span><span class="p">):</span>
        <span class="sd">&quot;&quot;&quot;Set the element by index, sll[index]=val</span>

<span class="sd">        Time complexity: O(n)</span>
<span class="sd">        &quot;&quot;&quot;</span>
        <span class="k">assert</span> <span class="mi">0</span> <span class="o">&lt;=</span> <span class="n">index</span> <span class="o">&lt;=</span> <span class="p">(</span><span class="nb">len</span><span class="p">(</span><span class="bp">self</span><span class="p">)</span> <span class="o">-</span> <span class="mi">1</span><span class="p">),</span> <span class="s2">&quot;Index out of range&quot;</span>
        <span class="n">p</span> <span class="o">=</span> <span class="bp">self</span><span class="o">.</span><span class="n">head</span>
        <span class="k">while</span> <span class="n">index</span> <span class="o">&gt;</span> <span class="mi">0</span><span class="p">:</span>
            <span class="n">p</span> <span class="o">=</span> <span class="n">p</span><span class="o">.</span><span class="n">next</span>
            <span class="n">index</span> <span class="o">-=</span> <span class="mi">1</span>
        <span class="n">p</span><span class="o">.</span><span class="n">value</span> <span class="o">=</span> <span class="n">val</span>

<div class="viewcode-block" id="Singlellist.is_empty"><a class="viewcode-back" href="../../toydata.html#toydata.LinkedLists.Singlellist.is_empty">[docs]</a>    <span class="k">def</span> <span class="nf">is_empty</span><span class="p">(</span><span class="bp">self</span><span class="p">):</span>
        <span class="sd">&quot;&quot;&quot;If the list is empty or not</span>

<span class="sd">        Time complexity: O(1)</span>
<span class="sd">        &quot;&quot;&quot;</span>
        <span class="k">return</span> <span class="bp">self</span><span class="o">.</span><span class="n">size</span> <span class="o">==</span> <span class="mi">0</span></div>

<div class="viewcode-block" id="Singlellist.add_first"><a class="viewcode-back" href="../../toydata.html#toydata.LinkedLists.Singlellist.add_first">[docs]</a>    <span class="k">def</span> <span class="nf">add_first</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">value</span><span class="p">):</span>
        <span class="sd">&quot;&quot;&quot;</span>
<span class="sd">        Inserting an element at the head of a single linked list</span>

<span class="sd">        Time complexity: O(1)</span>
<span class="sd">        &quot;&quot;&quot;</span>
        <span class="n">new_node</span> <span class="o">=</span> <span class="n">Node</span><span class="p">(</span><span class="n">value</span><span class="p">)</span>
        <span class="c1"># empty list</span>
        <span class="k">if</span> <span class="bp">self</span><span class="o">.</span><span class="n">is_empty</span><span class="p">():</span>
            <span class="bp">self</span><span class="o">.</span><span class="n">head</span> <span class="o">=</span> <span class="n">new_node</span>
            <span class="bp">self</span><span class="o">.</span><span class="n">tail</span> <span class="o">=</span> <span class="n">new_node</span>
        <span class="k">else</span><span class="p">:</span>
            <span class="n">new_node</span><span class="o">.</span><span class="n">next</span> <span class="o">=</span> <span class="bp">self</span><span class="o">.</span><span class="n">head</span>
            <span class="bp">self</span><span class="o">.</span><span class="n">head</span> <span class="o">=</span> <span class="n">new_node</span>
        <span class="bp">self</span><span class="o">.</span><span class="n">size</span> <span class="o">+=</span> <span class="mi">1</span></div>

<div class="viewcode-block" id="Singlellist.add_last"><a class="viewcode-back" href="../../toydata.html#toydata.LinkedLists.Singlellist.add_last">[docs]</a>    <span class="k">def</span> <span class="nf">add_last</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">value</span><span class="p">):</span>
        <span class="sd">&quot;&quot;&quot;</span>
<span class="sd">        Adding element at the end of single linked list</span>

<span class="sd">        Time complexity: O(1)</span>
<span class="sd">        &quot;&quot;&quot;</span>
        <span class="n">new_node</span> <span class="o">=</span> <span class="n">Node</span><span class="p">(</span><span class="n">value</span><span class="p">)</span>
        <span class="c1"># empty list</span>
        <span class="k">if</span> <span class="bp">self</span><span class="o">.</span><span class="n">is_empty</span><span class="p">():</span>
            <span class="bp">self</span><span class="o">.</span><span class="n">head</span> <span class="o">=</span> <span class="n">new_node</span>
            <span class="bp">self</span><span class="o">.</span><span class="n">tail</span> <span class="o">=</span> <span class="n">new_node</span>
        <span class="k">else</span><span class="p">:</span>
            <span class="bp">self</span><span class="o">.</span><span class="n">tail</span><span class="o">.</span><span class="n">next</span> <span class="o">=</span> <span class="n">new_node</span>
            <span class="bp">self</span><span class="o">.</span><span class="n">tail</span> <span class="o">=</span> <span class="n">new_node</span>
        <span class="bp">self</span><span class="o">.</span><span class="n">size</span> <span class="o">+=</span> <span class="mi">1</span></div>

<div class="viewcode-block" id="Singlellist.insert_after"><a class="viewcode-back" href="../../toydata.html#toydata.LinkedLists.Singlellist.insert_after">[docs]</a>    <span class="k">def</span> <span class="nf">insert_after</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">pos_value</span><span class="p">,</span> <span class="n">insert_value</span><span class="p">):</span>
        <span class="sd">&quot;&quot;&quot;</span>
<span class="sd">        Insert the insert_value after the (first)pos_value</span>

<span class="sd">        Time complexity: O(n)</span>
<span class="sd">        &quot;&quot;&quot;</span>
        <span class="k">assert</span> <span class="n">pos_value</span> <span class="ow">in</span> <span class="bp">self</span><span class="p">,</span> <span class="sa">f</span><span class="s2">&quot;There is no </span><span class="si">{pos_value}</span><span class="s2"> in list&quot;</span>
        <span class="n">insert_node</span> <span class="o">=</span> <span class="n">Node</span><span class="p">(</span><span class="n">insert_value</span><span class="p">)</span>
        <span class="n">pointer</span> <span class="o">=</span> <span class="bp">self</span><span class="o">.</span><span class="n">head</span>
        <span class="k">while</span> <span class="n">pointer</span><span class="o">.</span><span class="n">value</span> <span class="o">!=</span> <span class="n">pos_value</span><span class="p">:</span>
            <span class="n">pointer</span> <span class="o">=</span> <span class="n">pointer</span><span class="o">.</span><span class="n">next</span>
        <span class="n">insert_node</span><span class="o">.</span><span class="n">next</span> <span class="o">=</span> <span class="n">pointer</span><span class="o">.</span><span class="n">next</span>
        <span class="n">pointer</span><span class="o">.</span><span class="n">next</span> <span class="o">=</span> <span class="n">insert_node</span>
        <span class="bp">self</span><span class="o">.</span><span class="n">size</span> <span class="o">+=</span> <span class="mi">1</span></div>

<div class="viewcode-block" id="Singlellist.remove_first"><a class="viewcode-back" href="../../toydata.html#toydata.LinkedLists.Singlellist.remove_first">[docs]</a>    <span class="k">def</span> <span class="nf">remove_first</span><span class="p">(</span><span class="bp">self</span><span class="p">):</span>
        <span class="sd">&quot;&quot;&quot;</span>
<span class="sd">        Remove the first element in the single linked list.</span>
<span class="sd">        Or raise an empty error when there is no node in the list.</span>

<span class="sd">        Time complexity: O(1)</span>
<span class="sd">        &quot;&quot;&quot;</span>
        <span class="k">if</span> <span class="bp">self</span><span class="o">.</span><span class="n">is_empty</span><span class="p">():</span>
            <span class="k">raise</span> <span class="n">Empty</span><span class="p">(</span><span class="s2">&quot;The single linked list is empty&quot;</span><span class="p">)</span>
        <span class="n">answer</span> <span class="o">=</span> <span class="bp">self</span><span class="o">.</span><span class="n">head</span>
        <span class="bp">self</span><span class="o">.</span><span class="n">head</span> <span class="o">=</span> <span class="bp">self</span><span class="o">.</span><span class="n">head</span><span class="o">.</span><span class="n">next</span>
        <span class="bp">self</span><span class="o">.</span><span class="n">size</span> <span class="o">-=</span> <span class="mi">1</span>
        <span class="k">return</span> <span class="n">answer</span></div>

<div class="viewcode-block" id="Singlellist.remove_last"><a class="viewcode-back" href="../../toydata.html#toydata.LinkedLists.Singlellist.remove_last">[docs]</a>    <span class="k">def</span> <span class="nf">remove_last</span><span class="p">(</span><span class="bp">self</span><span class="p">):</span>
        <span class="sd">&quot;&quot;&quot;</span>
<span class="sd">        Remove the last element in the single linked list.</span>
<span class="sd">        Or raise an empty error when there is no node in the list.</span>

<span class="sd">        Time complexity: O(n)</span>
<span class="sd">        &quot;&quot;&quot;</span>
        <span class="k">if</span> <span class="bp">self</span><span class="o">.</span><span class="n">is_empty</span><span class="p">():</span>
            <span class="k">raise</span> <span class="n">Empty</span><span class="p">(</span><span class="s2">&quot;The single linked list is empty&quot;</span><span class="p">)</span>
        <span class="n">answer</span> <span class="o">=</span> <span class="bp">self</span><span class="o">.</span><span class="n">tail</span>
        <span class="c1"># when head = tail, we should change head too.</span>
        <span class="k">if</span> <span class="bp">self</span><span class="o">.</span><span class="n">size</span> <span class="o">==</span> <span class="mi">1</span><span class="p">:</span>
            <span class="bp">self</span><span class="o">.</span><span class="n">head</span> <span class="o">=</span> <span class="kc">None</span>
            <span class="bp">self</span><span class="o">.</span><span class="n">tail</span> <span class="o">=</span> <span class="kc">None</span>
        <span class="k">else</span><span class="p">:</span>
            <span class="n">pointer</span> <span class="o">=</span> <span class="bp">self</span><span class="o">.</span><span class="n">head</span>
            <span class="k">while</span> <span class="n">pointer</span><span class="o">.</span><span class="n">next</span> <span class="o">!=</span> <span class="bp">self</span><span class="o">.</span><span class="n">tail</span><span class="p">:</span>
                <span class="n">pointer</span> <span class="o">=</span> <span class="n">pointer</span><span class="o">.</span><span class="n">next</span>
            <span class="bp">self</span><span class="o">.</span><span class="n">tail</span> <span class="o">=</span> <span class="n">pointer</span>
            <span class="bp">self</span><span class="o">.</span><span class="n">tail</span><span class="o">.</span><span class="n">next</span> <span class="o">=</span> <span class="kc">None</span>
        <span class="bp">self</span><span class="o">.</span><span class="n">size</span> <span class="o">-=</span> <span class="mi">1</span>
        <span class="k">return</span> <span class="n">answer</span></div>

<div class="viewcode-block" id="Singlellist.remove"><a class="viewcode-back" href="../../toydata.html#toydata.LinkedLists.Singlellist.remove">[docs]</a>    <span class="k">def</span> <span class="nf">remove</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">val</span><span class="p">):</span>
        <span class="sd">&quot;&quot;&quot;</span>
<span class="sd">        Remove the first node with value equals to val.</span>

<span class="sd">        Time complexity: O(n)</span>
<span class="sd">        &quot;&quot;&quot;</span>
        <span class="k">assert</span> <span class="n">val</span> <span class="ow">in</span> <span class="bp">self</span><span class="p">,</span> <span class="sa">f</span><span class="s2">&quot;</span><span class="si">{val}</span><span class="s2"> don&#39;t in list!&quot;</span>
        <span class="n">p</span> <span class="o">=</span> <span class="bp">self</span><span class="o">.</span><span class="n">head</span>
        <span class="c1"># val in the head of the list</span>
        <span class="k">if</span> <span class="n">p</span><span class="o">.</span><span class="n">value</span> <span class="o">==</span> <span class="n">val</span><span class="p">:</span>
            <span class="bp">self</span><span class="o">.</span><span class="n">remove_first</span><span class="p">()</span>
        <span class="k">else</span><span class="p">:</span>
            <span class="k">while</span> <span class="n">p</span><span class="o">.</span><span class="n">next</span><span class="o">.</span><span class="n">value</span> <span class="o">!=</span> <span class="n">val</span><span class="p">:</span>
                <span class="n">p</span> <span class="o">=</span> <span class="n">p</span><span class="o">.</span><span class="n">next</span>
            <span class="c1"># val in the end of the list</span>
            <span class="k">if</span> <span class="n">p</span><span class="o">.</span><span class="n">next</span><span class="o">.</span><span class="n">next</span> <span class="ow">is</span> <span class="kc">None</span><span class="p">:</span>
                <span class="bp">self</span><span class="o">.</span><span class="n">tail</span> <span class="o">=</span> <span class="n">p</span>
            <span class="n">p</span><span class="o">.</span><span class="n">next</span> <span class="o">=</span> <span class="n">p</span><span class="o">.</span><span class="n">next</span><span class="o">.</span><span class="n">next</span>
            <span class="bp">self</span><span class="o">.</span><span class="n">size</span> <span class="o">-=</span> <span class="mi">1</span></div>

<div class="viewcode-block" id="Singlellist.remove_all"><a class="viewcode-back" href="../../toydata.html#toydata.LinkedLists.Singlellist.remove_all">[docs]</a>    <span class="k">def</span> <span class="nf">remove_all</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">val</span><span class="p">):</span>
        <span class="sd">&quot;&quot;&quot;</span>
<span class="sd">        Remove all the node woth value = val</span>

<span class="sd">        Note that we can do it in O(n), but we used an efficient</span>
<span class="sd">        algorithm here.</span>
<span class="sd">        &quot;&quot;&quot;</span>
        <span class="k">while</span> <span class="n">val</span> <span class="ow">in</span> <span class="bp">self</span><span class="p">:</span>
            <span class="bp">self</span><span class="o">.</span><span class="n">remove</span><span class="p">(</span><span class="n">val</span><span class="p">)</span></div>

<div class="viewcode-block" id="Singlellist.change"><a class="viewcode-back" href="../../toydata.html#toydata.LinkedLists.Singlellist.change">[docs]</a>    <span class="k">def</span> <span class="nf">change</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">old_val</span><span class="p">,</span> <span class="n">new_val</span><span class="p">):</span>
        <span class="sd">&quot;&quot;&quot;</span>
<span class="sd">        Change the first node with value &quot;old_val&quot; to &quot;new_val&quot;</span>

<span class="sd">        Time complexity: O(n)</span>
<span class="sd">        &quot;&quot;&quot;</span>
        <span class="k">assert</span> <span class="n">old_val</span> <span class="ow">in</span> <span class="bp">self</span><span class="p">,</span> <span class="sa">f</span><span class="s2">&quot;</span><span class="si">{old_val}</span><span class="s2"> not in list!&quot;</span>
        <span class="n">p</span> <span class="o">=</span> <span class="bp">self</span><span class="o">.</span><span class="n">head</span>
        <span class="k">while</span> <span class="n">p</span><span class="o">.</span><span class="n">value</span> <span class="o">!=</span> <span class="n">old_val</span><span class="p">:</span>
            <span class="n">p</span> <span class="o">=</span> <span class="n">p</span><span class="o">.</span><span class="n">next</span>
        <span class="n">p</span><span class="o">.</span><span class="n">value</span> <span class="o">=</span> <span class="n">new_val</span></div>

<div class="viewcode-block" id="Singlellist.change_all"><a class="viewcode-back" href="../../toydata.html#toydata.LinkedLists.Singlellist.change_all">[docs]</a>    <span class="k">def</span> <span class="nf">change_all</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">old_val</span><span class="p">,</span> <span class="n">new_val</span><span class="p">):</span>
        <span class="sd">&quot;&quot;&quot;</span>
<span class="sd">        Change all the node with &quot;old_val&quot; to &quot;new_val&quot;</span>

<span class="sd">        Note that we can do it in O(n), but we used an efficient</span>
<span class="sd">        algorithm here.</span>
<span class="sd">        &quot;&quot;&quot;</span>
        <span class="k">while</span> <span class="n">old_val</span> <span class="ow">in</span> <span class="bp">self</span><span class="p">:</span>
            <span class="bp">self</span><span class="o">.</span><span class="n">change</span><span class="p">(</span><span class="n">old_val</span><span class="p">,</span> <span class="n">new_val</span><span class="p">)</span></div>

<div class="viewcode-block" id="Singlellist.search"><a class="viewcode-back" href="../../toydata.html#toydata.LinkedLists.Singlellist.search">[docs]</a>    <span class="k">def</span> <span class="nf">search</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">value</span><span class="p">):</span>
        <span class="sd">&quot;&quot;&quot;</span>
<span class="sd">        If value in list or not.</span>

<span class="sd">        Time complexity: O(n)</span>
<span class="sd">        &quot;&quot;&quot;</span>
        <span class="k">return</span> <span class="n">value</span> <span class="ow">in</span> <span class="bp">self</span></div></div>


<div class="viewcode-block" id="Doublellist"><a class="viewcode-back" href="../../toydata.html#toydata.LinkedLists.Doublellist">[docs]</a><span class="k">class</span> <span class="nc">Doublellist</span><span class="p">:</span>
    <span class="sd">&quot;&quot;&quot;Double linked list(with sentinels)&quot;&quot;&quot;</span>

    <span class="k">class</span> <span class="nc">_Node</span><span class="p">:</span>
        <span class="sd">&quot;&quot;&quot;Lightweight, nonpublic class for storing a</span>
<span class="sd">        doubly linked node.&quot;&quot;&quot;</span>
        <span class="c1"># streamline memory</span>
        <span class="vm">__slots__</span> <span class="o">=</span> <span class="s1">&#39;_element&#39;</span><span class="p">,</span> <span class="s1">&#39;_prev&#39;</span><span class="p">,</span> <span class="s1">&#39;_next&#39;</span>

        <span class="k">def</span> <span class="fm">__init__</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">element</span><span class="p">,</span> <span class="n">prev</span><span class="p">,</span> <span class="nb">next</span><span class="p">):</span>
            <span class="sd">&quot;&quot;&quot;Create a Node&quot;&quot;&quot;</span>
            <span class="bp">self</span><span class="o">.</span><span class="n">_element</span> <span class="o">=</span> <span class="n">element</span>
            <span class="bp">self</span><span class="o">.</span><span class="n">_prev</span> <span class="o">=</span> <span class="n">prev</span>
            <span class="bp">self</span><span class="o">.</span><span class="n">_next</span> <span class="o">=</span> <span class="nb">next</span>

        <span class="k">def</span> <span class="fm">__str__</span><span class="p">(</span><span class="bp">self</span><span class="p">):</span>
            <span class="sd">&quot;&quot;&quot;Show the node in double linked list properly.&quot;&quot;&quot;</span>
            <span class="k">return</span> <span class="sa">f</span><span class="s2">&quot;</span><span class="si">{self._element}</span><span class="s2">&quot;</span>

    <span class="k">def</span> <span class="fm">__init__</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">items</span><span class="o">=</span><span class="kc">None</span><span class="p">):</span>
        <span class="sd">&quot;&quot;&quot;Create a empty list&quot;&quot;&quot;</span>
        <span class="bp">self</span><span class="o">.</span><span class="n">_header</span> <span class="o">=</span> <span class="bp">self</span><span class="o">.</span><span class="n">_Node</span><span class="p">(</span><span class="kc">None</span><span class="p">,</span> <span class="kc">None</span><span class="p">,</span> <span class="kc">None</span><span class="p">)</span>
        <span class="bp">self</span><span class="o">.</span><span class="n">_tailer</span> <span class="o">=</span> <span class="bp">self</span><span class="o">.</span><span class="n">_Node</span><span class="p">(</span><span class="kc">None</span><span class="p">,</span> <span class="kc">None</span><span class="p">,</span> <span class="kc">None</span><span class="p">)</span>
        <span class="bp">self</span><span class="o">.</span><span class="n">_size</span> <span class="o">=</span> <span class="mi">0</span>
        <span class="c1"># note that we must link the header and tailer firstly</span>
        <span class="bp">self</span><span class="o">.</span><span class="n">_header</span><span class="o">.</span><span class="n">_next</span> <span class="o">=</span> <span class="bp">self</span><span class="o">.</span><span class="n">_tailer</span>
        <span class="bp">self</span><span class="o">.</span><span class="n">_tailer</span><span class="o">.</span><span class="n">_prev</span> <span class="o">=</span> <span class="bp">self</span><span class="o">.</span><span class="n">_header</span>
        <span class="k">if</span> <span class="n">items</span><span class="p">:</span>
            <span class="k">for</span> <span class="n">item</span> <span class="ow">in</span> <span class="n">items</span><span class="p">:</span>
                <span class="bp">self</span><span class="o">.</span><span class="n">add_last</span><span class="p">(</span><span class="n">item</span><span class="p">)</span>

<div class="viewcode-block" id="Doublellist.is_empty"><a class="viewcode-back" href="../../toydata.html#toydata.LinkedLists.Doublellist.is_empty">[docs]</a>    <span class="k">def</span> <span class="nf">is_empty</span><span class="p">(</span><span class="bp">self</span><span class="p">):</span>
        <span class="sd">&quot;&quot;&quot;If the list is empty or not</span>

<span class="sd">        Time complexity: O(1)</span>
<span class="sd">        &quot;&quot;&quot;</span>
        <span class="k">return</span> <span class="bp">self</span><span class="o">.</span><span class="n">_size</span> <span class="o">==</span> <span class="mi">0</span></div>

    <span class="k">def</span> <span class="fm">__len__</span><span class="p">(</span><span class="bp">self</span><span class="p">):</span>
        <span class="sd">&quot;&quot;&quot;Return the size of the list</span>

<span class="sd">        Time complexity: O(1)</span>
<span class="sd">        &quot;&quot;&quot;</span>
        <span class="k">return</span> <span class="bp">self</span><span class="o">.</span><span class="n">_size</span>

    <span class="k">def</span> <span class="fm">__str__</span><span class="p">(</span><span class="bp">self</span><span class="p">):</span>
        <span class="sd">&quot;&quot;&quot;Show the double linked list properly.</span>

<span class="sd">        Time complexity: O(n)</span>
<span class="sd">        &quot;&quot;&quot;</span>
        <span class="n">result</span> <span class="o">=</span> <span class="s1">&#39;&#39;</span>
        <span class="n">result</span> <span class="o">+=</span> <span class="s1">&#39;Header&#39;</span>
        <span class="k">if</span> <span class="ow">not</span> <span class="bp">self</span><span class="o">.</span><span class="n">is_empty</span><span class="p">():</span>
            <span class="n">ptr</span> <span class="o">=</span> <span class="bp">self</span><span class="o">.</span><span class="n">_header</span><span class="o">.</span><span class="n">_next</span>
            <span class="k">while</span> <span class="n">ptr</span><span class="o">.</span><span class="n">_element</span> <span class="ow">is</span> <span class="ow">not</span> <span class="kc">None</span><span class="p">:</span>
                <span class="n">result</span> <span class="o">+=</span> <span class="s1">&#39;-&gt;&#39;</span> <span class="o">+</span> <span class="nb">str</span><span class="p">(</span><span class="n">ptr</span><span class="p">)</span>
                <span class="n">ptr</span> <span class="o">=</span> <span class="n">ptr</span><span class="o">.</span><span class="n">_next</span>
        <span class="n">result</span> <span class="o">+=</span> <span class="s1">&#39;-&gt;Tailer&#39;</span>
        <span class="k">return</span> <span class="n">result</span>

    <span class="k">def</span> <span class="fm">__contains__</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">val</span><span class="p">):</span>
        <span class="sd">&quot;&quot;&quot;If val in list or not</span>

<span class="sd">        Time complexity: O(n)</span>
<span class="sd">        &quot;&quot;&quot;</span>
        <span class="n">ptr</span> <span class="o">=</span> <span class="bp">self</span><span class="o">.</span><span class="n">_header</span>
        <span class="n">i</span> <span class="o">=</span> <span class="bp">self</span><span class="o">.</span><span class="n">_size</span>
        <span class="k">while</span> <span class="n">i</span> <span class="o">&gt;</span> <span class="mi">0</span><span class="p">:</span>
            <span class="k">if</span> <span class="n">ptr</span><span class="o">.</span><span class="n">_next</span><span class="o">.</span><span class="n">_element</span> <span class="o">==</span> <span class="n">val</span><span class="p">:</span>
                <span class="k">return</span> <span class="kc">True</span>
            <span class="n">ptr</span> <span class="o">=</span> <span class="n">ptr</span><span class="o">.</span><span class="n">_next</span>
            <span class="n">i</span> <span class="o">-=</span> <span class="mi">1</span>
        <span class="k">return</span> <span class="kc">False</span>

<div class="viewcode-block" id="Doublellist.first"><a class="viewcode-back" href="../../toydata.html#toydata.LinkedLists.Doublellist.first">[docs]</a>    <span class="k">def</span> <span class="nf">first</span><span class="p">(</span><span class="bp">self</span><span class="p">):</span>
        <span class="sd">&quot;&quot;&quot;Return the first value in the list.</span>
<span class="sd">        Or raise Empty error if the list is empty.</span>

<span class="sd">        Time complexity: O(1)</span>
<span class="sd">        &quot;&quot;&quot;</span>
        <span class="k">if</span> <span class="bp">self</span><span class="o">.</span><span class="n">_size</span> <span class="o">==</span> <span class="mi">0</span><span class="p">:</span>
            <span class="k">raise</span> <span class="n">Empty</span><span class="p">(</span><span class="s1">&#39;The list is empty!&#39;</span><span class="p">)</span>
        <span class="k">return</span> <span class="bp">self</span><span class="o">.</span><span class="n">_header</span><span class="o">.</span><span class="n">_next</span><span class="o">.</span><span class="n">_element</span></div>

<div class="viewcode-block" id="Doublellist.last"><a class="viewcode-back" href="../../toydata.html#toydata.LinkedLists.Doublellist.last">[docs]</a>    <span class="k">def</span> <span class="nf">last</span><span class="p">(</span><span class="bp">self</span><span class="p">):</span>
        <span class="sd">&quot;&quot;&quot;Return the last value in the list.</span>
<span class="sd">        Or raise Empty error if the list is empty.</span>

<span class="sd">        Time complexity: O(1)</span>
<span class="sd">        &quot;&quot;&quot;</span>
        <span class="k">if</span> <span class="bp">self</span><span class="o">.</span><span class="n">_size</span> <span class="o">==</span> <span class="mi">0</span><span class="p">:</span>
            <span class="k">raise</span> <span class="n">Empty</span><span class="p">(</span><span class="s1">&#39;The list is empty!&#39;</span><span class="p">)</span>
        <span class="k">return</span> <span class="bp">self</span><span class="o">.</span><span class="n">_tailer</span><span class="o">.</span><span class="n">_prev</span><span class="o">.</span><span class="n">_element</span></div>

<div class="viewcode-block" id="Doublellist.add_first"><a class="viewcode-back" href="../../toydata.html#toydata.LinkedLists.Doublellist.add_first">[docs]</a>    <span class="k">def</span> <span class="nf">add_first</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">e</span><span class="p">):</span>
        <span class="sd">&quot;&quot;&quot;</span>
<span class="sd">        Add a node at the first of the list.</span>

<span class="sd">        Time complexity: O(1)</span>
<span class="sd">        &quot;&quot;&quot;</span>
        <span class="n">new_node</span> <span class="o">=</span> <span class="bp">self</span><span class="o">.</span><span class="n">_Node</span><span class="p">(</span><span class="n">e</span><span class="p">,</span> <span class="bp">self</span><span class="o">.</span><span class="n">_header</span><span class="p">,</span> <span class="bp">self</span><span class="o">.</span><span class="n">_header</span><span class="o">.</span><span class="n">_next</span><span class="p">)</span>
        <span class="bp">self</span><span class="o">.</span><span class="n">_header</span><span class="o">.</span><span class="n">_next</span><span class="o">.</span><span class="n">_prev</span> <span class="o">=</span> <span class="n">new_node</span>
        <span class="bp">self</span><span class="o">.</span><span class="n">_header</span><span class="o">.</span><span class="n">_next</span> <span class="o">=</span> <span class="n">new_node</span>
        <span class="bp">self</span><span class="o">.</span><span class="n">_size</span> <span class="o">+=</span> <span class="mi">1</span></div>

<div class="viewcode-block" id="Doublellist.add_last"><a class="viewcode-back" href="../../toydata.html#toydata.LinkedLists.Doublellist.add_last">[docs]</a>    <span class="k">def</span> <span class="nf">add_last</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">e</span><span class="p">):</span>
        <span class="sd">&quot;&quot;&quot;Add a node at the last of the list</span>

<span class="sd">        Time complexity: O(1)</span>
<span class="sd">        &quot;&quot;&quot;</span>
        <span class="n">new_node</span> <span class="o">=</span> <span class="bp">self</span><span class="o">.</span><span class="n">_Node</span><span class="p">(</span><span class="n">e</span><span class="p">,</span> <span class="bp">self</span><span class="o">.</span><span class="n">_tailer</span><span class="o">.</span><span class="n">_prev</span><span class="p">,</span> <span class="bp">self</span><span class="o">.</span><span class="n">_tailer</span><span class="p">)</span>
        <span class="bp">self</span><span class="o">.</span><span class="n">_tailer</span><span class="o">.</span><span class="n">_prev</span><span class="o">.</span><span class="n">_next</span> <span class="o">=</span> <span class="n">new_node</span>
        <span class="bp">self</span><span class="o">.</span><span class="n">_tailer</span><span class="o">.</span><span class="n">_prev</span> <span class="o">=</span> <span class="n">new_node</span>
        <span class="bp">self</span><span class="o">.</span><span class="n">_size</span> <span class="o">+=</span> <span class="mi">1</span></div>

<div class="viewcode-block" id="Doublellist.insert_after"><a class="viewcode-back" href="../../toydata.html#toydata.LinkedLists.Doublellist.insert_after">[docs]</a>    <span class="k">def</span> <span class="nf">insert_after</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">pos_val</span><span class="p">,</span> <span class="n">ins_val</span><span class="p">):</span>
        <span class="sd">&quot;&quot;&quot;</span>
<span class="sd">        Insert `ins_val` after `pos_val`</span>

<span class="sd">        Time complexity: O(n)</span>
<span class="sd">        &quot;&quot;&quot;</span>
        <span class="c1"># make sure there are a pos_val in list</span>
        <span class="k">assert</span> <span class="n">pos_val</span> <span class="ow">in</span> <span class="bp">self</span><span class="p">,</span> <span class="sa">f</span><span class="s2">&quot;</span><span class="si">{pos_val}</span><span class="s2"> not in list!&quot;</span>
        <span class="n">ptr</span> <span class="o">=</span> <span class="bp">self</span><span class="o">.</span><span class="n">_header</span>
        <span class="k">while</span> <span class="n">ptr</span><span class="o">.</span><span class="n">_element</span> <span class="o">!=</span> <span class="n">pos_val</span><span class="p">:</span>
            <span class="n">ptr</span> <span class="o">=</span> <span class="n">ptr</span><span class="o">.</span><span class="n">_next</span>
        <span class="n">new_node</span> <span class="o">=</span> <span class="bp">self</span><span class="o">.</span><span class="n">_Node</span><span class="p">(</span><span class="n">ins_val</span><span class="p">,</span> <span class="n">ptr</span><span class="p">,</span> <span class="n">ptr</span><span class="o">.</span><span class="n">_next</span><span class="p">)</span>
        <span class="n">ptr</span><span class="o">.</span><span class="n">_next</span><span class="o">.</span><span class="n">_prev</span> <span class="o">=</span> <span class="n">new_node</span>
        <span class="n">ptr</span><span class="o">.</span><span class="n">_next</span> <span class="o">=</span> <span class="n">new_node</span>
        <span class="bp">self</span><span class="o">.</span><span class="n">_size</span> <span class="o">+=</span> <span class="mi">1</span></div>

<div class="viewcode-block" id="Doublellist.remove_first"><a class="viewcode-back" href="../../toydata.html#toydata.LinkedLists.Doublellist.remove_first">[docs]</a>    <span class="k">def</span> <span class="nf">remove_first</span><span class="p">(</span><span class="bp">self</span><span class="p">):</span>
        <span class="sd">&quot;&quot;&quot;</span>
<span class="sd">        Remove the first node of the list.</span>
<span class="sd">        Or raise an Empty error if the list is empty.</span>

<span class="sd">        Time complexity: O(1)</span>
<span class="sd">        &quot;&quot;&quot;</span>
        <span class="k">if</span> <span class="bp">self</span><span class="o">.</span><span class="n">is_empty</span><span class="p">():</span>
            <span class="k">raise</span> <span class="n">Empty</span><span class="p">(</span><span class="s2">&quot;The list is empty!&quot;</span><span class="p">)</span>
        <span class="n">element</span> <span class="o">=</span> <span class="bp">self</span><span class="o">.</span><span class="n">first</span><span class="p">()</span>
        <span class="bp">self</span><span class="o">.</span><span class="n">_header</span><span class="o">.</span><span class="n">_next</span><span class="o">.</span><span class="n">_next</span><span class="o">.</span><span class="n">_prev</span> <span class="o">=</span> <span class="bp">self</span><span class="o">.</span><span class="n">_header</span>
        <span class="bp">self</span><span class="o">.</span><span class="n">_header</span><span class="o">.</span><span class="n">_next</span> <span class="o">=</span> <span class="bp">self</span><span class="o">.</span><span class="n">_header</span><span class="o">.</span><span class="n">_next</span><span class="o">.</span><span class="n">_next</span>
        <span class="bp">self</span><span class="o">.</span><span class="n">_size</span> <span class="o">-=</span> <span class="mi">1</span>
        <span class="k">return</span> <span class="n">element</span></div>

<div class="viewcode-block" id="Doublellist.remove_last"><a class="viewcode-back" href="../../toydata.html#toydata.LinkedLists.Doublellist.remove_last">[docs]</a>    <span class="k">def</span> <span class="nf">remove_last</span><span class="p">(</span><span class="bp">self</span><span class="p">):</span>
        <span class="sd">&quot;&quot;&quot;Remove the last node of the list</span>

<span class="sd">        Time complexity: O(1)&quot;&quot;&quot;</span>
        <span class="k">if</span> <span class="bp">self</span><span class="o">.</span><span class="n">is_empty</span><span class="p">():</span>
            <span class="k">raise</span> <span class="n">Empty</span><span class="p">(</span><span class="s2">&quot;The list is empty!&quot;</span><span class="p">)</span>
        <span class="n">element</span> <span class="o">=</span> <span class="bp">self</span><span class="o">.</span><span class="n">first</span><span class="p">()</span>
        <span class="bp">self</span><span class="o">.</span><span class="n">_tailer</span><span class="o">.</span><span class="n">_prev</span><span class="o">.</span><span class="n">_prev</span> <span class="o">=</span> <span class="bp">self</span><span class="o">.</span><span class="n">_tailer</span>
        <span class="bp">self</span><span class="o">.</span><span class="n">_tailer</span><span class="o">.</span><span class="n">_prev</span> <span class="o">=</span> <span class="bp">self</span><span class="o">.</span><span class="n">_tailer</span><span class="o">.</span><span class="n">_prev</span><span class="o">.</span><span class="n">_prev</span>
        <span class="bp">self</span><span class="o">.</span><span class="n">_size</span> <span class="o">-=</span> <span class="mi">1</span>
        <span class="k">return</span> <span class="n">element</span></div>

<div class="viewcode-block" id="Doublellist.remove"><a class="viewcode-back" href="../../toydata.html#toydata.LinkedLists.Doublellist.remove">[docs]</a>    <span class="k">def</span> <span class="nf">remove</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">val</span><span class="p">):</span>
        <span class="sd">&quot;&quot;&quot;</span>
<span class="sd">        Only remove the first node with value equals `val`</span>

<span class="sd">        Time complexity: O(n)</span>
<span class="sd">        &quot;&quot;&quot;</span>
        <span class="k">assert</span> <span class="n">val</span> <span class="ow">in</span> <span class="bp">self</span><span class="p">,</span> <span class="sa">f</span><span class="s2">&quot;</span><span class="si">{val}</span><span class="s2"> not in list!&quot;</span>
        <span class="n">ptr</span> <span class="o">=</span> <span class="bp">self</span><span class="o">.</span><span class="n">_header</span>
        <span class="k">while</span> <span class="n">ptr</span><span class="o">.</span><span class="n">_next</span><span class="o">.</span><span class="n">_element</span> <span class="o">!=</span> <span class="n">val</span><span class="p">:</span>
            <span class="n">ptr</span> <span class="o">=</span> <span class="n">ptr</span><span class="o">.</span><span class="n">_next</span>
        <span class="n">ptr</span><span class="o">.</span><span class="n">_next</span><span class="o">.</span><span class="n">_next</span><span class="o">.</span><span class="n">_prev</span> <span class="o">=</span> <span class="n">ptr</span>
        <span class="n">ptr</span><span class="o">.</span><span class="n">_next</span> <span class="o">=</span> <span class="n">ptr</span><span class="o">.</span><span class="n">_next</span><span class="o">.</span><span class="n">_next</span>
        <span class="bp">self</span><span class="o">.</span><span class="n">_size</span> <span class="o">-=</span> <span class="mi">1</span></div>

<div class="viewcode-block" id="Doublellist.remove_all"><a class="viewcode-back" href="../../toydata.html#toydata.LinkedLists.Doublellist.remove_all">[docs]</a>    <span class="k">def</span> <span class="nf">remove_all</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">val</span><span class="p">):</span>
        <span class="sd">&quot;&quot;&quot;</span>
<span class="sd">        Remove all the nodes with value equals `val`</span>

<span class="sd">        Note: here we use an efficient way to do that</span>
<span class="sd">        &quot;&quot;&quot;</span>
        <span class="k">while</span> <span class="n">val</span> <span class="ow">in</span> <span class="bp">self</span><span class="p">:</span>
            <span class="bp">self</span><span class="o">.</span><span class="n">remove</span><span class="p">(</span><span class="n">val</span><span class="p">)</span></div>

<div class="viewcode-block" id="Doublellist.change"><a class="viewcode-back" href="../../toydata.html#toydata.LinkedLists.Doublellist.change">[docs]</a>    <span class="k">def</span> <span class="nf">change</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">old_val</span><span class="p">,</span> <span class="n">new_val</span><span class="p">):</span>
        <span class="sd">&quot;&quot;&quot;</span>
<span class="sd">        Only change the first node with `old_val` to `new_val`</span>

<span class="sd">        Time complexity: O(n)</span>
<span class="sd">        &quot;&quot;&quot;</span>
        <span class="n">ptr</span> <span class="o">=</span> <span class="bp">self</span><span class="o">.</span><span class="n">_header</span>
        <span class="k">while</span> <span class="n">ptr</span><span class="o">.</span><span class="n">_next</span><span class="o">.</span><span class="n">_element</span> <span class="o">!=</span> <span class="n">old_val</span><span class="p">:</span>
            <span class="n">ptr</span> <span class="o">=</span> <span class="n">ptr</span><span class="o">.</span><span class="n">_next</span>
        <span class="n">ptr</span><span class="o">.</span><span class="n">_next</span><span class="o">.</span><span class="n">_element</span> <span class="o">=</span> <span class="n">new_val</span></div>

<div class="viewcode-block" id="Doublellist.change_all"><a class="viewcode-back" href="../../toydata.html#toydata.LinkedLists.Doublellist.change_all">[docs]</a>    <span class="k">def</span> <span class="nf">change_all</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">old_val</span><span class="p">,</span> <span class="n">new_val</span><span class="p">):</span>
        <span class="sd">&quot;&quot;&quot;</span>
<span class="sd">        Change all the node with `old_val` to `new_val`</span>

<span class="sd">        Note: here we use an efficient way to do that</span>
<span class="sd">        &quot;&quot;&quot;</span>
        <span class="k">while</span> <span class="n">old_val</span> <span class="ow">in</span> <span class="bp">self</span><span class="p">:</span>
            <span class="bp">self</span><span class="o">.</span><span class="n">change</span><span class="p">(</span><span class="n">old_val</span><span class="p">,</span> <span class="n">new_val</span><span class="p">)</span></div>

<div class="viewcode-block" id="Doublellist.search"><a class="viewcode-back" href="../../toydata.html#toydata.LinkedLists.Doublellist.search">[docs]</a>    <span class="k">def</span> <span class="nf">search</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">val</span><span class="p">):</span>
        <span class="sd">&quot;&quot;&quot;If val in list of not</span>

<span class="sd">        Time complexity: O(n)</span>
<span class="sd">        &quot;&quot;&quot;</span>
        <span class="k">return</span> <span class="n">val</span> <span class="ow">in</span> <span class="bp">self</span></div></div>
</pre></div>

           </div>
           
          </div>
          <footer>
  

  <hr/>

  <div role="contentinfo">
    <p>
        &copy; Copyright 2019, Xiangzhuang Shen

    </p>
  </div>
  Built with <a href="http://sphinx-doc.org/">Sphinx</a> using a <a href="https://github.com/rtfd/sphinx_rtd_theme">theme</a> provided by <a href="https://readthedocs.org">Read the Docs</a>. 

</footer>

        </div>
      </div>

    </section>

  </div>
  


  <script type="text/javascript">
      jQuery(function () {
          SphinxRtdTheme.Navigation.enable(true);
      });
  </script>

  
  
    
   

</body>
</html>